<!DOCTYPE html>
<html>
	<head>
		<meta charset="UTF-8">
		<title></title>
	</head>
	<body>
		<!--归并排序
		解析:
		归并排序是一种稳定的排序方法。
		将已有序的子序列合并，得到完全有序的序列；
		即先使每个子序列有序，再使子序列段间有序。-->
		<script type="text/javascript">
			function mergeSort(arr) { // 采用自上而下的递归方法
				var len = arr.length;
				if (len < 2) {
					return arr;
				}
				var middle = Math.floor(len / 2),
					left = arr.slice(0, middle),
					right = arr.slice(middle);
				return merge(mergeSort(left), mergeSort(right));
			}
			
			function merge(left, right) {
				var result = [];
				console.time('归并排序耗时');
				while(left.length && right.length) {
					if (left[0] <= right[0]) {
						result.push(left.shift())
					} else {
						result.push(right.shift());
					}
				}
				while(left.length) {
					result.push(left.shift());
				}
				while(right.length) {
					result.push(right.shift());
				}
				console.timeEnd('归并排序耗时');
				return result;
			}
			var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
			document.write(mergeSort(arr));
		</script>
	</body>
</html>
